/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package problemset3helper;

import java.io.File;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;

/**
 *
 * @author Chandan
 */
public class ProblemSet3newCode {

    /**
     * @param args the command line arguments
     */
    static int m;
    static int n;

    public static void main(String[] args) {
        // TODO code application logic here

        try {
//            Scanner in = new Scanner(new File("1"));
//            Scanner in = new Scanner(new File("1_1"));
//            Scanner in = new Scanner(new File("1_2"));
//            Scanner in = new Scanner(new File("2"));
            Scanner in = new Scanner(new File("3"));
//            Scanner in = new Scanner(new File("4"));
//            Scanner in = new Scanner(new File("4_1"));
//            Scanner in = new Scanner(new File("4_2"));
//            Scanner in = new Scanner(new File("4_3"));
            int M = in.nextInt();
            int N = in.nextInt();
            m = M;
            n = N;
            String[] input = new String[N * M];
            int x = 0;
            in.nextLine();
            while (in.hasNextLine()) {
                input[x] = in.nextLine().replaceAll(" ", "");
                x++;
            }
            Board(M, N, input);

            generateData();
//            giveMeBest("0", "", 0, 0);
//            System.out.println("PossibleList : " + possibleList);
//            int least = Integer.MAX_VALUE;
//            String leastPossibility = "";
//            for (Iterator<String> it = possibleList.iterator(); it.hasNext();) {
//                String string = it.next();
//                String[] split = string.split("R");
//                if (least > split.length - 1) {
//                    least = split.length - 1;
//                    leastPossibility = string;
//                }
//            }
            System.out.println("Least : " + least);
            System.out.println("Least : " + Integer.toBinaryString(least).length());
            System.out.println("Least Possibility : " + leastPossibility);

        } catch (Exception ex) {
            System.out.println(ex.getMessage());
        }
    }
    static problemset3helper.Tile[][] board;

    private static void generateData() {

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
//                System.out.println("========================================");
//                System.out.print(board.board[i][j].toString() + " ");
                //===========================================================
                ArrayList<problemset3helper.Tile> choices = getMovableTiles(board[i][j].m, board[i][j].n);
                for (Tile tile : choices) {
                    board[i][j].paths.add("" + tile.tileValue);
                }
                //System.out.println("R0 : " + board.board[i][j].paths + " ");
                //===========================================================
                board[i][j].rotate();
                choices = getMovableTiles(board[i][j].m, board[i][j].n);
                for (Tile tile : choices) {
                    board[i][j].paths.add("R" + tile.tileValue);
                }
                //System.out.println("R1 : " + board.board[i][j].paths);
                //===========================================================
                board[i][j].rotate();
                choices = getMovableTiles(board[i][j].m, board[i][j].n);
                for (Tile tile : choices) {
                    board[i][j].paths.add("RR" + tile.tileValue);
                }
                //System.out.println("R2 : " + board.board[i][j].paths);
                //===========================================================
                board[i][j].rotate();
                choices = getMovableTiles(board[i][j].m, board[i][j].n);
                for (Tile tile : choices) {
                    board[i][j].paths.add("RRR" + tile.tileValue);
                }
                //System.out.println("R3 : " + board.board[i][j].paths);
//                System.out.println(board[i][j].paths);
                board[i][j].rotate();
            }
        }
    }
    static ArrayList<String> possibleList = new ArrayList<>();
    static int least = Integer.MAX_VALUE;
    static String leastPossibility = "";

    static void giveMeBest(String data, String path, int m, int n) {
        if (path.equals(getTargetValue())) {
            possibleList.add(data);
            String[] split = data.split("R");
            if (least > split.length - 1) {
                least = split.length - 1;
                leastPossibility = data;

            }
        }
        for (Iterator<String> it = board[m][n].paths.iterator(); it.hasNext();) {
            String check = it.next();
            String go1 = check.replaceAll("R", "");
            if (!data.contains(go1)) {
                String tempData = data + check;
                int k = Integer.parseInt(go1);
                boolean pass = true;
                for (int i = 0; i < ProblemSet3newCode.m && pass; i++) {
                    if (board[i][ProblemSet3newCode.n - 1].value >= k) {
                        for (int j = 0; j < ProblemSet3newCode.n && pass; j++) {
                            if (board[i][j].tileValue.equals(go1)) {
                                m = board[i][j].m;
                                n = board[i][j].n;
                                pass = false;

                            }
                        }
                    }
                }
                giveMeBest(tempData, go1, m, n);
            }
        }
    }

    static ArrayList<Tile> getMovableTiles(int mp, int np) {
        ArrayList<Tile> passibleMoves = new ArrayList<>();
        try {
            if (board[mp][np].topPart == board[mp - 1][np].bottomPart) {
                passibleMoves.add(board[mp - 1][np]);
            }
        } catch (Exception e) {
        }
        try {
            if (board[mp][np].rightPart == board[mp][np + 1].leftPart) {
                passibleMoves.add(board[mp][np + 1]);
            }
        } catch (Exception e) {
        }
        try {
            if (board[mp][np].bottomPart == board[mp + 1][np].topPart) {
                passibleMoves.add(board[mp + 1][np]);
            }
        } catch (Exception e) {
        }
        try {
            if (board[mp][np].leftPart == board[mp][np - 1].rightPart) {
                passibleMoves.add(board[mp][np - 1]);
            }
        } catch (Exception e) {
        }
        return passibleMoves;
    }

    static void Board(int M, int N, String[] chars) {
        int tileValue = 0;
        ProblemSet3newCode.board = new Tile[M][N];
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                Tile tile = new Tile(chars[tileValue], tileValue, "" + tileValue++, i, j);
                board[i][j] = tile;
            }
        }
    }

    static String getTargetValue() {
        return "" + ((board.length * board[0].length) - 1);
    }
}